#include <bits/stdc++.h>
#include "BinarySearchTree.h"
using namespace std;

clock_t tbegin,tend;

template<typename T>
void BST_sort(vector<T>& _data){
    BinarySearchTree<T> data;
    tbegin=clock();
    for(auto x:_data){
        data.insert(x);
    }
    data.vectorprint(_data);
    tend=clock();
}

template<typename T>
void Randomized_BST_sort(vector<T>& _data){
    BinarySearchTree<T> data;
    tbegin=clock();
    random_shuffle(_data.begin(),_data.end());
    for(auto x:_data){
        data.insert(x);
    }
    data.vectorprint(_data);
    tend=clock();
}

template<typename T>
bool isEqual(vector<T>& A,vector<T>& B){
    if(A.size()!=B.size()) return false;
    for(int i=0;i<(int)A.size();i++){
        if(A[i]!=B[i]) return false;
    }
    return true;
}

int main(){
    cerr<<endl<<"Lets's start our test"<<endl;
    //input a vecot;
    int n,number;
    double time;
    vector<int> input,copy,sort1,sort2,standard;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>number;
        input.push_back(number);
    }
    copy=input;
    //test 1
    BST_sort(input);
    time=(double)(tend-tbegin)/CLOCKS_PER_SEC;
    cerr<<"The time of BST_sort is "<<time<<endl;
    sort1=input;
    //test 2
    input=copy;
    Randomized_BST_sort(input);
    time=(double)(tend-tbegin)/CLOCKS_PER_SEC;
    cerr<<"The time of RandomizedBST_sort is "<<time<<endl;
    sort2=input;
    //standard test
    input=copy;
    tbegin=clock();
    sort(input.begin(),input.end());
    tend=clock();
    time=(double)(tend-tbegin)/CLOCKS_PER_SEC;
    cerr<<"The time of system's sort is "<<time<<endl;
    standard=input;
    //check
    cerr<<endl;
    if(isEqual(sort1,standard)) cerr<<"BST_sort succeeds!"<<endl;
    else cerr<<"BST_sort fails!"<<endl;
    if(isEqual(sort1,standard)) cerr<<"RandomizedBST_sort succeeds!"<<endl;
    else cerr<<"RandomsizedBST_sort fails!"<<endl;
    //out
    for(auto x:standard){
        cout<<setw(6)<<setiosflags(ios::left)<<x;
    }
    cout<<endl;
    cerr<<endl<<"Sorted vector already printed, goodbye!"<<endl;
    return 0;
}